class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m = len(p)  # 表达式长度
        n = len(s)  # 被匹配字符串长度

        # 初始化dp数组 ，最前面多加一行一列
        dp = [[False for _ in range(n + 1)] for _ in range(m + 1)]

        # 一个虚拟的初始的匹配起点
        dp[0][0] = True

        if p.startswith("*"):# *开头则任意字符都可匹配
            dp[1] = [True] * (n + 1)

        for i in range(1, m + 1):
            flag = False # *之后全匹配的标志
            for j in range(1, n + 1):
                if p[i - 1] == '*':
                    if dp[i - 1][0] == True: # 这里是处理*或多个*在p起始位置可以是空串的问题
                        dp[i] = [True] * (n + 1) # 如果不给dp[i][0]位置赋True值，下一个非*字符做头部时会失效
                    if dp[i - 1][j] == True:
                        flag = True
                    if flag:
                        dp[i][j] = True
                elif p[i - 1] == '?' or p[i - 1] == s[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    pass
        # print(dp)

        return dp[-1][-1]


if __name__ == "__main__":
    mySol = Solution()
    al = [1, 2, 3, 2, 1, 0, 1]
    bl = [3, 2, 1, 0, 1, 4, 7]
    mystr = 'abcdefghijk'
    s = 'abc'
    p = 'ac'
    # al = [0, 0, 0, 0, 1]
    # bl = [1, 0, 0, 0, 0]
    print('feedback:', mySol.isMatch(s, p))
